package com.hy;

import java.util.Arrays;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:最接近的三数之和
 *
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。
 * 假定每组输入只存在恰好一个解。
 *
 * User:Mr.Du
 * Date:2024/8/17
 * Time:16:29
 */
public class ThreeSumClosest {

    /**
     * 寻找数组中三个数的和，使得这个和最接近目标值
     * 通过排序和双指针法来实现，先对数组排序，然后遍历数组，固定一个数，使用双指针找出最接近目标值的三个数的和
     *
     * @param nums 输入的整数数组
     * @param target 目标值
     * @return 返回最接近目标值的三个数的和
     */
    public int threeSumClosest(int[] nums, int target) {
        // 初始化结果为0，差值g为一个较大的数，用于记录当前最接近目标值的差值
        int res = 0, n = nums.length, g = 100000;
        // 对数组进行排序，以便后续使用双指针法
        Arrays.sort(nums);
        // 遍历数组，固定一个数，使用双指针找出最接近目标值的三个数的和
        for(int i = 0;i < n - 2;i++){
            int x = nums[i];
            // 跳过重复的数，避免重复计算
            if(i > 0 && x == nums[i-1]) continue;
            // 计算当前固定数与后面两个数的和，判断是否已经超过目标值
            int s = x + nums[i+1] + nums[i+2];
            if(s > target){
                // 如果超过目标值的差值小于当前最接近目标值的差值g，则更新结果和差值g
                if(s - target < g){
                    res = s;
                }
                // 如果已经超过目标值，则不再继续遍历后面的数，跳出循环
                break;
            }
            // 计算当前固定数与最后两个数的和，判断是否小于目标值
            s = x + nums[n-2] + nums[n-1];
            if(s < target){
                // 如果小于目标值的差值小于当前最接近目标值的差值g，则更新结果和差值g
                if(target - s < g){
                    g = target - s;
                    res = s;
                }
                // 继续遍历下一个数
                continue;
            }
            // 使用双指针法，j指向当前数的下一个数，k指向数组最后一个数
            int j = i + 1;
            int k = n - 1;
            // 当j小于k时，执行双指针法
            while(j < k){
                // 计算当前三个数的和
                s = x + nums[j] + nums[k];
                // 计算与目标值的差
                int y = s - target;
                // 如果差为0，则已经找到目标值，直接返回结果
                if(y == 0) return s;
                // 如果差大于0，说明和大于目标值，将k指针左移
                else if(y > 0){
                    k--;
                }
                // 如果差小于0，说明和小于目标值，将j指针右移
                else{
                    j++;
                }
                // 如果当前差的绝对值小于最接近目标值的差值g，则更新结果和差值g
                if(Math.abs(y) < g){
                    res = s;
                    g = Math.abs(y);
                }
            }
        }
        // 返回最接近目标值的三个数的和
        return res;
    }

}
